public class Test {
    public void majorityElement(int[] nums) {
        mergeSort(nums);

    }
    //归并排序
    public static void mergeSort(int[] array) {
        mergeSortFun(array,0,array.length-1);
    }

    public static void mergeSortFun(int[] array,int left,int right) {
        if(left >= right) {// >
            return;
        }
        int mid = (right+left) / 2;
        mergeSortFun(array,left,mid);
        mergeSortFun(array,mid+1,right);
        //合并
        merge(array,left,mid,right);
    }
    private static void merge(int[] array,int left,
                              int mid,int right) {
        int[] tmp = new int[right-left+1];
        int k = 0;
        int s1 = left;
        int e1 = mid;
        int s2 = mid+1;
        int e2 = right;
        while (s1 <= e1 && s2 <= e2) {
            if(array[s1] <= array[s2]) {
                tmp[k++] = array[s1++];
            }else {
                tmp[k++] = array[s2++];
            }
        }
        while (s1 <= e1) {
            tmp[k++] = array[s1++];
        }
        while (s2 <= e2) {
            tmp[k++] = array[s2++];
        }
        //走到这里 相当于tmp数组 当中 所有的元素 都有序了
        //接下来把tmp数组的内容 拷贝到array数组当中
        for (int i = 0; i < k; i++) {
            array[i+left] = tmp[i];
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1,2,3,2,5,5,5,7,88,66,9};
        Test s = new Test();
        s.majorityElement(nums);
        System.out.println(nums[nums.length / 2]);
    }
}
